#include <stdio.h>
#include <stdlib.h>

typedef int E;

struct BTreeNode0 {
    E element;
    struct BTreeNode0 *left;
    struct BTreeNode0 *right;
    int height;
};

typedef struct BTreeNode0 *Node;

Node createNode(E element) {
    Node node = (Node) malloc(sizeof(struct BTreeNode0));
    node->right = node->left = NULL;
    node->element = element;
    return node;
}

int max(int a, int b) {
    return a > b ? a : b;
}

int getHeight(Node root) {
    if (root == NULL) return 0;
    return root->height;
}

Node leftRotation(Node root) {  //左旋操作，实际上就是把左边结点拿上来
    Node newRoot = root->right;   //先得到左边结点
    root->right = newRoot->left;   //将左边结点的左子树丢到原本根结点的右边去
    newRoot->left = root;   //现在新的根结点左边就是原本的跟结点了

    root->height = max(getHeight(root->right), getHeight(root->left)) + 1;
    newRoot->height = max(getHeight(newRoot->right), getHeight(newRoot->left)) + 1;
    return newRoot;
}

Node rightRotation(Node root) {
    Node newRoot = root->left;
    root->left = newRoot->right;
    newRoot->right = root;

    root->height = max(getHeight(root->right), getHeight(root->left)) + 1;
    newRoot->height = max(getHeight(newRoot->right), getHeight(newRoot->left)) + 1;
    return newRoot;
}

Node leftRightRotation(Node root) {
    root->left = leftRotation(root->left);
    return rightRotation(root);
}

Node rightLeftRightRotation(Node root) {
    root->right = rightRotation(root->right);
    return leftRotation(root);
}

Node insert(Node root, E element) {
    //如果结点为NULL，说明找到了插入位置，直接创建新的就完事
    // 和二叉搜索树一样，判断大小，该走哪边走哪边，直到找到对应插入位置
    if (root == NULL) root = createNode(element);
    else if (root->element > element) {
        root->left = insert(root->left, element);
        //插入完成之后，需要计算平衡因子，看看是否失衡
        if (getHeight(root->left) - getHeight(root->right) > 1) {
            if (root->left->element > element) root = rightRotation(root);
            else root = leftRightRotation(root);
        }
    } else if (root->element < element) {
        root->right = insert(root->right, element);
        if (getHeight(root->left) - getHeight(root->right) < -1) {
            if (root->right->element < element)
                root = leftRotation(root);
            else
                root = rightLeftRightRotation(root);
        }
    }
    //前面的操作完成之后记得更新一下树高度
    root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
    //最后返回root到上一级
    return root;
}

void inOrder(Node root){
    if(root == NULL) return;
    inOrder(root->left);
    printf("%d ", root->element);
    inOrder(root->right);
}

int main() {
    Node root = NULL;
    while (1){
        E e;
        scanf("%d",&e);
        if (e == -1) break;
        root = insert(root,e);
        inOrder(root);
        printf("\n");
    }
}
